<?php
/**
 * 插入排序 - 希尔排序(shell's sort)
 * O(n log2 n)
 * @param array $seq A list of integers
 * @return array Return sorted array
 */

function shell_sort($seq)
{
    for ($gap = count($seq) >> 1; $gap > 0; $gap >>= 1) {
        for ($i = $gap; $i < count($seq); $i++) {
            $temp = $seq[$i];
            for ($j = $i - $gap; $j >= 0 && $seq[$j] > $temp; $j -= $gap) {
                $seq[$j + $gap] = $seq[$j];
            }
            $seq[$j + $gap] = $temp;
        }
    }

    return $seq;
}
